package com.zwj.interview.两数和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 输入一个数组，如何找出数组中所有和为0的3个数字的三元组？需要注意的是，
 * 返回值中不得包含重复的三元组。例如，在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，
 * 它们分别是[-1，0，1]和[-1，-1，2]
 * <p>
 * https://leetcode.cn/problems/3sum/
 */
public class 三数和为0 {

    /**
     * 如果输入的数组是排序的，就可以先固定一个数字i，
     * 然后在排序数组中查找和为-i的两个数字。我们已经有了用O（n）时间在排序数组中找出和为给定值的两个数字的方法，
     * 由于需要固定数组中的每个数字，因此查找三元组的时间复杂度是O（n2）
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int target = 0;
        Arrays.sort(nums);
        if (nums.length < 3) {
            return result;
        }
        //固定i,推进j,k两个下标
        for (int i = 0; i < nums.length; i++) {
            //跳过重复数字
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] < target) {
                    j++;
                    //跳过重复,没有必要重复比较
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                } else if (nums[i] + nums[j] + nums[k] > target) {
                    k--;
                    //同样跳过重复，没有必要重复比较
                    while (j < k && nums[k] == nums[k +1]) {
                        k--;
                    }
                } else {
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}
